package _11_整理题目._6_模拟设计;

import org.junit.Test;

/**
 * https://leetcode-cn.com/problems/compare-version-numbers/
 * 
 * 比较规则：版本号有修订号构成，用 . 连接，从左到右逐个比较每个修订号，
 * v1 > v2，返回 1；
 * v1 < v2，返回 -1；
 * v1 = v2，返回 0；
 * 
 * 思路一：
 *      首先将字符串按 . 分割为 字符串数组；
 *      逐个转换每个元素为 int，比较
 *      如果两个数组长度不一致，短的补 0
 *      此时空间复杂度 O(n)
 *
 * 思路二：
 *      通过双指针，一边遍历，一边解析每个 . 之前的版本号，并比较
 * 
 * 注意：
 * string.split(regex, limit) : 根据规则 regex，将 string 分为 n 个元素的字符串数组，n 可选
 * . | * $   点竖星刀 等转义字符需要加 \\，java 中 \ 用 \\ 表示
 * string.split("\\.")      按照 . 分割
 * string.split("\\|")      按照 | 分割
 * string.split("\\*")      按照 * 分割
 * string.split("\\$")      按照 $ 分割
 * 
 * string.split("-")        按照 - 分割
 * 
 */
public class _02_比较版本号 {

    // 先分割，再解析比较
    public int compareVersion(String version1, String version2) {
        String[] strings1 = version1.split("\\.");
        String[] strings2 = version2.split("\\.");
        int len1 = strings1.length;
        int len2 = strings2.length;

        for(int i=0; i<len1 || i<len2; i++) {
            int num1 = i<len1 ? Integer.parseInt(strings1[i]) : 0;
            int num2 = i<len2 ? Integer.parseInt(strings2[i]) : 0;
            if(num1 > num2) {
                return 1;
            } else if(num1 < num2) {
                return -1;
            }
        }
        return 0;
    }

    // 双指针
    public int compareVersion2(String version1, String version2) {
        int m = version1.length();
        int n = version2.length();
        int i=0, j=0;
        while(i<m || j<n) {
            int x = 0;
            for(; i<m && version1.charAt(i)!='.'; i++) {
                x = x * 10 + (version1.charAt(i)-'0');
            }
            i++;

            int y = 0;
            for(; j<n && version2.charAt(j)!='.'; j++) {
                y = y * 10 + (version2.charAt(j)-'0');
            }
            j++;

            if(x > y) {
                return 1;
            } else if(x < y) {
                return -1;
            }
        }
        return 0;
    }
    
    @Test
    public void main() {
        String version1 = "1.01";
        String version2 = "1.001";
        System.out.println(compareVersion(version1, version2));
    }
}
